namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0977. 有序数组的平方")]
    public class No0977_SortedSquares : AbsBaseTestItem
    {
        /*
        给定一个按非递减顺序排序的整数数组 A，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。
        提示：
            1 <= A.length <= 10000
            -10000 <= A[i] <= 10000
            A 已按非递减顺序排序。
        */

        public override void OnTest()
        {
            Assert.TestExe(SortedSquares,
                new int[] { -4, -1, 0, 3, 10 },
                new int[] { 0, 1, 9, 16, 100 });

            Assert.TestExe(SortedSquares,
                new int[] { -7, -3, 2, 3, 11 },
                new int[] { 4, 9, 9, 49, 121 });
        }

        public int[] SortedSquares(int[] A)
        {
            int n = A.Length;
            int[] ans = new int[n];
            for (int i = 0, j = n - 1, pos = n - 1; i <= j;)
            {
                var iv = A[i] * A[i];
                var jv = A[j] * A[j];
                if (iv > jv)
                {
                    ans[pos] = iv;
                    i++;
                }
                else
                {
                    ans[pos] = jv;
                    j--;
                }
                pos--;
            }
            return ans;
        }
    }
}
